package _2022.hot100._114_二叉树展开为链表;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author： YHSimon
 * @date： 2022-04-27 16:06
 */

/**
 * 114.二叉树展开为链表
 */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {

    // 迭代
    public void flatten2(TreeNode root){
        List<TreeNode> list=new ArrayList<>();
        Deque<TreeNode> stack=new LinkedList<>();
        TreeNode node=root;
        while(node!=null||!stack.isEmpty()){
            while(node!=null){
                list.add(node);
                stack.push(node);
                node=node.left;
            }
            node=stack.pop();
            node=node.right;
        }

        int size=list.size();
        for(int i=1;i<size;i++){
            TreeNode pre=list.get(i-1),cur=list.get(i);
            pre.left=null;
            pre.right=cur;
        }
    }

    // 递归形式
    public void flatten(TreeNode root) {
        List<TreeNode> list=new ArrayList<>();
        preOrder(root, list);
        for(int i=1;i<list.size();++i){
            TreeNode prev=list.get(i-1),curr=list.get(i);
            prev.left=null;
            prev.right=curr;
        }
    }

    public void preOrder(TreeNode node,List<TreeNode> list) {
        if(node==null){
            return;
        }
        list.add(node);
        preOrder(node.left, list);
        preOrder(node.right, list);
    }

    public static void main(String[] args) {

    }
}
